from 图的实现 import Graph


def genLegalMoves(x, y, bdSize):
    newmove = []
    moveOffsets = [(-1, -2), (-1, 2), (-2, -1), (-2, 1),
                   (1, -2), (1, 2), (2, -1), (2, 1)]
    for i in moveOffsets:
        newx = x + i[0]
        newy = y + i[0]
        if legalCoord(newx, bdSize) and legalCoord(newy, bdSize):
            newmove.append((newx, newy))
        return newmove


def legalCoord(x, bdSize):  # 确认不会走出棋盘
    if x >= 0 and x < bdSize:
        return True
    else:
        return False


def knightGraph(bdsize):
    ktGraph = Graph()
    for row in range(bdsize):  # 遍历每个格子
        for col in range(bdsize):
            nodeId = posToNodeId(row, col, bdsize)
            newpositions = genLegalMoves(row, col, bdsize)
            for e in newpositions:
                nid = posToNodeId(e[0], e[1], bdsize)
                ktGraph.addEdge(nodeId, nid)
    return ktGraph


def posToNodeId(row, col, bdsize):
    return row * bdsize + col
